The Total Coloring Conjecture (TCC) proposes that every simple graph G is (Δ + 2)-totally-colorable, where Δ is the maximum degree of G. For planar graph, TCC is open only in case Δ = 6. In this paper, we prove tha...The Total Coloring Conjecture (TCC) proposes that every simple graph G is (Δ + 2)-totally-colorable, where Δ is the maximum degree of G. For planar graph, TCC is open only in case Δ = 6. In this paper, we prove that TCC holds for planar graph with Δ = 6 and every 7-cycle contains at most two chords.展开更多
In the minimum degree vertex deletion problem,we are given a graph,a distinguished vertex in the graph,and an integer κ,and the question is whether we can delete at most κ vertices from the graph so that the disting...In the minimum degree vertex deletion problem,we are given a graph,a distinguished vertex in the graph,and an integer κ,and the question is whether we can delete at most κ vertices from the graph so that the distinguished vertex has the unique minimum degree.The maximum degree vertex deletion problem is defined analogously but here we want the distinguished vertex to have the unique maximum degree.It is known that both problems areΨ-hard and fixed-parameter intractable with respect to some natural parameters.In this paper,we study the(parameterized)complexity of these two problems restricted to split graphs,p-degenerate graphs,and planar graphs.Our study provides a comprehensive complexity landscape of the two problems restricted to these special graphs.展开更多
A coloring of graph G is an injective coloring if its restriction to the neighborhood of any vertex is injective, which means that any two vertices get different colors if they have a common neighbor. The injective ch...A coloring of graph G is an injective coloring if its restriction to the neighborhood of any vertex is injective, which means that any two vertices get different colors if they have a common neighbor. The injective chromatic number χi(G) of G is the least integer k such that G has an injective k-coloring. In this paper, we prove that(1) if G is a planar graph with girth g ≥ 6 and maximum degree △ ≥ 7, then χi(G) ≤ △ + 2;(2) if G is a planar graph with △ ≥ 24 and without 3,4,7-cycles, then χi(G) ≤ △ + 2.展开更多
文摘The Total Coloring Conjecture (TCC) proposes that every simple graph G is (Δ + 2)-totally-colorable, where Δ is the maximum degree of G. For planar graph, TCC is open only in case Δ = 6. In this paper, we prove that TCC holds for planar graph with Δ = 6 and every 7-cycle contains at most two chords.
文摘In the minimum degree vertex deletion problem,we are given a graph,a distinguished vertex in the graph,and an integer κ,and the question is whether we can delete at most κ vertices from the graph so that the distinguished vertex has the unique minimum degree.The maximum degree vertex deletion problem is defined analogously but here we want the distinguished vertex to have the unique maximum degree.It is known that both problems areΨ-hard and fixed-parameter intractable with respect to some natural parameters.In this paper,we study the(parameterized)complexity of these two problems restricted to split graphs,p-degenerate graphs,and planar graphs.Our study provides a comprehensive complexity landscape of the two problems restricted to these special graphs.
基金supported by the National Natural Science Foundation of China (No.11871377)。
文摘A coloring of graph G is an injective coloring if its restriction to the neighborhood of any vertex is injective, which means that any two vertices get different colors if they have a common neighbor. The injective chromatic number χi(G) of G is the least integer k such that G has an injective k-coloring. In this paper, we prove that(1) if G is a planar graph with girth g ≥ 6 and maximum degree △ ≥ 7, then χi(G) ≤ △ + 2;(2) if G is a planar graph with △ ≥ 24 and without 3,4,7-cycles, then χi(G) ≤ △ + 2.
