A structure of 1-planar graph and its applications to coloring problems

DOI10.1007/S00373-019-02027-0MaRDI QIDQ2000562zbMATHOpenAlexWikidataFDO

Authors Xin Zhang, Bei Niu, Jiguo Yu

Publication date 28 June 2019

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1902.08945

zbMATH Keywords

equitable edge coloring(\(p\)1)-total labelling

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Graph representations (geometric and intersection representations, etc.) (05C62) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Abstract: A graph is 1-planar if it can be drawn on a plane so that each edge is crossed by at most one other edge. In this paper, we first give a useful structural theorem for 1-planar graphs, and then apply it to the list edge and list total coloring, the $(p,1)$-total labelling, and the equitable edge coloring of 1-planar graphs. More precisely, we verify the well-known List Edge Coloring Conjecture and List Total Coloring Conjecture for 1-planar graph with maximum degree at least 18, prove that the $(p,1)$-total labelling number of every 1-planar graph $G$ is at most $Delta(G)+2p-2$ provided that $Delta(G)geq8p+2$ and $pgeq2$, and show that every 1-planar graph has an equitable edge coloring with $k$ colors for any integer $kgeq18$. These three results respectively generalize the main theorems of three different previously published papers.

Recommendations

• List edge and list total coloring of 1-planar graphs
• On total colorings of 1-planar graphs
• On total colorings of some special 1-planar graphs
• On edge colorings of \(1\)-planar graphs
• On \((p,1)\)-total labelling of 1-planar graphs

Cites work

• scientific article; zbMATH DE number 3900784 (Why is no real title available?)
• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• A new proof of the 6 color theorem
• An annotated bibliography on 1-planarity
• Ein Sechsfarbenproblem auf der Kugel
• Graph theory with applications
• List edge and list total coloring of 1-planar graphs
• List edge and list total colourings of multigraphs
• List-edge and list-total colorings of graphs embedded on hyperbolic surfaces
• On \((p,1)\)-total labelling of 1-planar graphs
• On \((p,1)\)-total labelling of planar graphs
• On edge colorings of 1-planar graphs without adjacent triangles
• On edge colorings of \(1\)-planar graphs
• On the equitable edge-coloring of 1-planar graphs and planar graphs
• On total colorings of 1-planar graphs
• The structure of 1-planar graphs
• \((d,1)\)-total labelling of planar graphs with large girth and high maximum degree
• \((p,1)\)-total labelling of graphs

Cited in

(8)

• Dynamic list coloring of 1-planar graphs
• On list \((p, 1)\)-total labellings of special planar graphs and 1-planar graphs
• A Facility Coloring Problem in 1-D
• 1-平面图的结构性质及其在无圈边染色上的应用
• On \((p, 1)\)-total labelling of some 1-planar graphs
• A note on total colorings of 1-planar graphs
• Equitable coloring of three classes of 1-planar graphs
• List edge and list total coloring of 1-planar graphs

This page was built for publication: A structure of 1-planar graph and its applications to coloring problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2000562)