On the minimum weight of a 3-connected 1-planar graph
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
A graph is called \emph{$1$-planar} if it can be drawn in the Euclidean plane $\mathbb{R}^2$ such that each edge is crossed by at most one other edge. The \emph{weight} of an edge is the sum of degrees of two ends. It is known that every planar graph of minimum degree $\delta\ge3$ has an edge with weight at most $13$. In the present paper, we show the existence of edges with weight at most $25$ in $3$-connected $1$-planar graphs.
Abstract
A graph is called \emph{$1$-planar} if it can be drawn in the Euclidean plane $\mathbb{R}^2$ such that each edge is crossed by at most one other edge. The \emph{weight} of an edge is the sum of degrees of two ends. It is known that every planar graph of minimum degree $\delta\ge3$ has an edge with weight at most $13$. In the present paper, we show the existence of edges with weight at most $25$ in $3$-connected $1$-planar graphs.
참고문헌 (12)
- J. A. Bondy, "Graph Theory" (2008), Springer
- O. V. Borodin, "Solution of the Ringel problems on vertex-face coloring of planar graphs and coloring of 1-planar graphs", Metody Discret. Anal, 41, pp.12~26 (1984)
- O. V. Borodin, "On the total coloring of planar graphs", J. Reine Angew. Math, 394, pp.180~185 (1989)
- O. V. Borodin, "Acyclic colouring of 1-planar graphs", Discrete Math, 114(1-3), pp.29~41 (2001)
- J. Czap, "On drawings and decompositions of 1-planar graphs", Electron. J. Combin, 20(2), pp.54~60 (2013)
- I. Fabrici, "The structure of 1-planar graphs", Discrete Math, 307(7-8), pp.854~865 (2007)
- B. Grunbaum, "New views on some old questions of combinatorial geometry, IColloquio Internazionale sulle Teorie Combinatorie (Rome, 1973), Tomo I", Atti dei Convegni Lincei, No. 17, Accad. Naz. Lincei, 451~468 (1976)
- D. Hudák, "Light edges in 1-planar graphs with prescribed minimum degree", Discuss. Math. Graph Theory, 32(3), pp.545~556 (2012)
- S. Jendrol, "Light subgraphs of graphs embedded in the plane - A survey", Discrete Math, 313(4), pp.406~421 (2013)
- A. Kotzig, "Contribution to the theory of Eulerian polyhedra", Mat.-Fyz. Časpis. Slovensk. Akad. Vied (Math. Slovaca), 5, pp.101~113 (1955)
- Xin Zhang, "Light 3-cycles in 1-planar graphs with degree restrictions", 대한수학회보, 51(2), pp.511~517 (2014), 대한수학회
- X. Zhang, "On edge colorings of 1-planar graphs", Inform. Process. Lett, 111(3), pp.124~128 (2011)