Bounds for the matching number, the edge chromatic number and the independence number of a graph in terms of rank

DOI10.1016/J.DAM.2013.09.012MaRDI QIDQ2636822zbMATH OpenOpenAlexFDO

Authors Long Wang, Dein Wong

Publication date 18 February 2014

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2013.09.012

zbMATH Keywords

matching numberindependence numberchromatic indexrank of graphs

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• scientific article; zbMATH DE number 6383843
• Bounds for the nullity of a graph in terms of the matching number and the independence number
• On the independence number of edge chromatic critical graphs
• Independence and matching number of some graphs
• A new upper bound for the independence number of edge chromatic critical graphs
• The independence number of an edge-chromatic critical graph
• Independence number of edge‐chromatic critical graphs
• Spectral Inequalities on Independence Number, Chromatic Number, and Total Chromatic Number of a Graph
• Bounds on the independence number of a graph in terms of order, size and maximum degree
• Bounds for the chromatic number of a graph

Cites work

• scientific article; zbMATH DE number 3717357 (Why is no real title available?)
• scientific article; zbMATH DE number 1983913 (Why is no real title available?)
• A Bound for the Chromatic Number of a Graph
• A characterization of graphs with rank 4
• A characterization of graphs with rank 5
• A counterexample to the rank-coloring conjecture
• A note on graphs with zero nullity
• Chromatic number and the 2-rank of a graph
• On nut and core singular fullerenes
• On the construction of graphs of nullity one
• On the nullity and the matching number of unicyclic graphs
• On the nullity of a graph with cut-points
• On the nullity of bipartite graphs
• On the nullity of bipartite graphs
• On the nullity of line graphs of trees
• Rank and chromatic number of a graph
• Spektren endlicher Grafen
• The gap between the chromatic number of a graph and the rank of its adjacency matrix is superlinear
• The rank of a graph after vertex addition
• Trees with maximum nullity

Cited in

(54)

• On connected graphs of order n with girth g and nullity n-g
• Bounds on the nullity, the \(H\)-rank and the Hermitian energy of a mixed graph
• The rank of a complex unit gain graph in terms of the rank and the independence number of its underlying graph
• The extremal graphs with respect to their nullity
• Relations between the inertia indices of a mixed graph and those of its underlying graph
• The rank of a complex unit gain graph in terms of the matching number
• On the relation between theH-rank of a mixed graph and the matching number of its underlying graph
• Relation between the nullity of a graph and its matching number
• Bounds for the rank of a complex unit gain graph in terms of its maximum degree
• Proof of a conjecture on the nullity of a graph
• Relation between the \(H\)-rank of a mixed graph and the rank of its underlying graph
• Characterization of graphs with given order, given size and given matching number that minimize nullity
• The relation between the \(H\)-rank of a mixed graph and the independence number of its underlying graph
• A characterization of graphs \(G\) with nullity \(|V(G)|-2m(G)+2c(G)\)
• An upper bound of the nullity of a graph in terms of order and maximum degree
• The nullities of signed cycle-spliced graphs
• A survey of the maximal and the minimal nullity in terms of omega invariant on graphs
• Relation between the inertia indices of a complex unit gain graph and those of its underlying graph
• Proof of a conjecture on the nullity of a connected graph in terms of order and maximum degree
• The rank of a signed graph
• No graph with nullity \(\eta(G) = | V(G) | - 2 m(G) + 2 c(G) - 1\)
• The leaf-free graphs with nullity \(2 c ( G ) - 1\)
• A sharp upper bound of the nullity of a connected graph in terms of order and maximum degree
• The multiplicity of an arbitrary eigenvalue of a graph in terms of cyclomatic number and number of pendant vertices
• The nullity of a graph with fractional matching number
• scientific article; zbMATH DE number 6383843 (Why is no real title available?)
• On the difference between the skew-rank of an oriented graph and the rank of its underlying graph
• Skew-rank of an oriented graph in terms of the rank and dimension of cycle space of its underlying graph
• The gap between the rank of a complex unit gain graph and its underlying graph
• Nullity of a graph in terms of path cover number
• Bounds for the matching number and cyclomatic number of a signed graph in terms of rank
• The rank of a complex unit gain graph in terms of the rank of its underlying graph
• Relation between the Hermitian energy of a mixed graph and the matching number of its underlying graph
• The rank of a signed graph in terms of the rank of its underlying graph
• A simpler sharp lower bound for nullity of a bipartite graph
• Improved bounds on the H-rank of a mixed graph in terms of the matching number and fractional matching number
• Bounds of nullity for complex unit gain graphs
• Nullity of a graph in terms of the dimension of cycle space and the number of pendant vertices
• Relation between the rank of a signed graph and the fractional matching number of its underlying graph
• On connected signed graphs with rank equal to girth
• No signed graph with the nullity \(\eta(G,\sigma)=|V(G)|-2m(G)+2c(G)-1\)
• Relationship between the rank and the matching number of a graph
• Characterization of graphs with rank 2v(G) - 2(G) - 2c(G) + 1
• scientific article; zbMATH DE number 7692350 (Why is no real title available?)
• The multiplicities of eigenvalues of a graph
• Nullities of graphs with given order, matching number and cyclomatic number revisited
• The multiplicity of nonzero eigenvalues and the induced matching number of a graph
• An upper bound for the nullity of a bipartite graph in terms of its maximum degree
• Inertia indices of a complex unit gain graph in terms of matching number
• A characterization of graphs with two types of eigenvalue multiplicities equal to n - d - 1
• Graphs \(G\) with nullity \(2c(G) + p(G) - 1\)
• Upper bounds of the energy of triangle-free graphs in terms of matching number
• Bounds for the rank of a complex unit gain graph in terms of the independence number
• An improved lower bound for the nullity of a graph in terms of matching number

This page was built for publication: Bounds for the matching number, the edge chromatic number and the independence number of a graph in terms of rank

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