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

DOI10.1007/S00373-019-02027-0zbMATH Open1416.05086arXiv1902.08945OpenAlexW3101621653WikidataQ128246452 ScholiaQ128246452MaRDI QIDQ2000562FDOQ2000562

Authors: Xin Zhang, Bei Niu, Jiguo Yu 

Publication date: 28 June 2019

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

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.

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

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

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)

Cites Work

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

Cited In (8)

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