Currently displaying 1 – 2 of 2

Showing per page

Order by Relevance | Title | Year of publication

1-planar graphs with girth at least 6 are (1,1,1,1)-colorable

Lili SongLei Sun — 2023

Czechoslovak Mathematical Journal

A graph is 1-planar if it can be drawn in the Euclidean plane so that each edge is crossed by at most one other edge. A 1-planar graph on n vertices is optimal if it has 4 n - 8 edges. We prove that 1-planar graphs with girth at least 6 are (1,1,1,1)-colorable (in the sense that each of the four color classes induces a subgraph of maximum degree one). Inspired by the decomposition of 1-planar graphs, we conjecture that every 1-planar graph is (2,2,2,0,0)-colorable.

Note on improper coloring of 1 -planar graphs

Yanan ChuLei SunJun Yue — 2019

Czechoslovak Mathematical Journal

A graph G = ( V , E ) is called improperly ( d 1 , , d k ) -colorable if the vertex set V can be partitioned into subsets V 1 , , V k such that the graph G [ V i ] induced by the vertices of V i has maximum degree at most d i for all 1 i k . In this paper, we mainly study the improper coloring of 1 -planar graphs and show that 1 -planar graphs with girth at least 7 are ( 2 , 0 , 0 , 0 ) -colorable.

Page 1

Download Results (CSV)