Chromatic Number of ISK4-Free Graphs

Le, Ngoc
November 2017
Graphs & Combinatorics;Nov2017, Vol. 33 Issue 6, p1635
Academic Journal
A graph G is said to be ISK4-free if it does not contain any subdivision of $$K_4$$ as an induced subgraph. In this paper, we propose new upper bounds for the chromatic number of ISK4-free graphs and $$\{$$ ISK4, triangle $$\}$$ -free graphs.


Related Articles

  • Further Properties of Trees with Minimal Atom-Bond Connectivity Index. Jianping Liu; Jinsong Chen // Abstract & Applied Analysis;2014, p1 

    Let G = (V, E) be a graph the atom-bond connectivity (ABC) index is defined as the sum of weights ((du + dv - 2 ) /dudv)1/2 over all edges uv of G, where du denotes the degree of a vertex u of G. In this paper, we determined a few structural features of the trees with minimal ABC index also we...

  • Independent Monopoly Size In Graphs. Naji, Ahmed Mohammed; Soner, N. D. // Applications & Applied Mathematics;Dec2015, Vol. 10 Issue 2, p738 

    In a graph G = (V;E), a set D ⊆ V (G) is said to be a monopoly set of G if every vertex v 2 V ∊D has at least d(v)/2 neighbors in D. The monopoly size of G, denoted mo(G), is the minimum cardinality of a monopoly set among all monopoly sets in G. The set D ⊆ V (G) is an...

  • Neighborhood Total 2-Domination in Graphs. Sivagnanam, C. // International Journal of Mathematical Combinatorics;Dec2014, Vol. 4, p108 

    Let G = (V,E) be a graph without isolated vertices. A set S ⊆ V is called the neighborhood total 2-dominating set (nt2d-set) of a graph G if every vertex in V − S is adjacent to at least two vertices in S and the induced subgraph < N(S) > has no isolated vertices. The minimum...

  • Some Minimal (r, 2, k)-Regular Graphs Containing a Given Graph and its Complement. Maheswari, N. R. Santhi; Sekar, C. // International Journal of Mathematical Combinatorics;Mar2015, Vol. 1, p65 

    A graph G is called (r, 2, k)-regular graph if each vertex of G is at a distance 1 away from r vertices of G and each vertex of G is at a distance 2 away from k vertices of G [9]. This paper suggest a method to construct a ((m+2(n−1)), 2, (m−1)(2n−1)))-regular graph H4 of...

  • On 3-Regular Bipancyclic Subgraphs of Hypercubes. Borse, Y. M.; Shaikh, S. R. // International Journal of Combinatorics;5/5/2015, Vol. 2015, p1 

    The n-dimensional hypercube Qn is bipancyclic; that is, it contains a cycle of every even length from 4 to 2n. In this paper, we prove that Qn  (n≥3) contains a 3-regular, 3-connected, bipancyclic subgraph with l vertices for every even l from 8 to 2n except 10.

  • Semitotal Domination in Claw-Free Cubic Graphs. Henning, Michael; Marcon, Alister // Annals of Combinatorics;Dec2016, Vol. 20 Issue 4, p799 

    In this paper, we continue the study of semitotal domination in graphs in [Discrete Math. 324, 13-18 (2014)]. A set $${S}$$ of vertices in $${G}$$ is a semitotal dominating set of $${G}$$ if it is a dominating set of $${G}$$ and every vertex in $${S}$$ is within distance 2 of another vertex of...

  • GRAPHS COSPECTRAL WITH A FRIENDSHIP GRAPH OR ITS COMPLEMENT. ABDOLLAHI, A.; JANBAZ, S.; OBOUDI, M. R. // Transactions on Combinatorics;2013, Vol. 2 Issue 4, p37 

    Let n be any positive integer and Fn be the friendship (or Dutch windmill) graph with 2n+1 vertices and 3n edges. Here we study graphs with the same adjacency spectrum as Fn. Two graphs are called cospectral if the eigenvalues multiset of their adjacency matrices are the same. Let G be a graph...

  • A note on neighborhood total domination in graphs. RAD, NADER JAFARI // Proceedings of the Indian Academy of Sciences: Mathematical Scie;Aug2015, Vol. 125 Issue 3, p271 

    Let G = (V,E) be a graph without isolated vertices. A dominating set S of G is called a neighborhood total dominating set (or just NTDS) if the induced subgraph G[N(S)] has no isolated vertex. The minimum cardinality of a NTDS of G is called the neighborhood total domination number of G and is...

  • On Zero-Sum and Almost Zero-Sum Subgraphs Over $${\mathbb {Z}}$$. Caro, Yair; Yuster, Raphael // Graphs & Combinatorics;Jan2016, Vol. 32 Issue 1, p49 

    For a graph $$H$$ with at most $$n$$ vertices and a weighing of the edges of $$K_n$$ with integers, we seek a copy of $$H$$ in $$K_n$$ whose weight is minimal, possibly even zero. Of a particular interest are the cases where $$H$$ is a spanning subgraph (or an almost spanning subgraph) and the...

  • Around The Berge Problem And Hadwiger Conjecture. Nemron, Ikorong Anouk Gilbert // International Journal of Mathematical Combinatorics;Jul2012, Vol. 3, p72 

    We say that a graph B is berge, if every graph B' ∈ {B,B̄} does not contain an induced cycle of odd length ≥ 5 [B̄ is the complementary graph of B]. A graph G is perfect if every induced subgraph G' of G satisfies χ(G ) = ω(G ), where χ(G') is the chromatic number...


Read the Article


Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics